package com.example.nirvana.dataStructure;


/**
 * 二叉树（有序）
 */
public class MyBinaryTree {
    private TreeNode root;

    public MyBinaryTree() {
        root = null; // 这里唯一的一句root=null;都可以省略.因为对象在初始化时,其成员变量默认初始值是空，这里加上是为了逻辑清晰
    }

    /**
     * 插入二叉树节点
     *
     * @param key
     * @param value
     */
    public void insert(int key, int value) {
        TreeNode newNode = new TreeNode(key, value);
        if(root == null) {
            root = newNode;
        }else {
            TreeNode current = root;
            while(true) {
                if(newNode.key < current.key) {
                    // 新节点在当前节点左子树上
                    current = current.left;
                }else {
                    // 新节点在当前节点右子树上
                    current = current.right;
                }
                // 找到对应位置并添加
                if(current == null) {
                    current = newNode;
                    return;
                }
            }
        }
    }

    /**
     * 获取二叉树节点
     *
     * @param key
     * @return
     * @throws Exception
     */
    public TreeNode getNode(int key) throws Exception {
        TreeNode result = root;
        while(result.key != key) {
            if(key < result.key) {
                result = result.left;
            }else {
                result = result.right;
            }
            if(result == null) {
                throw new Exception("Can`t find value by " + key);
            }
        }
        return result;
    }


}
